package com.datastructures2.graph.有向图;

/**
 * 顶点对的可达性
 * @author MaoLin Wang
 * @date 2020/2/2219:52
 */
public class TransitiveClosure {
    private DirectedDFS[] directedDFS;  // tc[v] = reachable from v

    /**
     * 构造函数
     * 所需空间与V²成正比
     * 所需时间与 V(V+E)成正比
     * @param G
     */
    public TransitiveClosure(Digraph G) {
        directedDFS = new DirectedDFS[G.V()];
        for (int v = 0; v < G.V(); v++)
            directedDFS[v] = new DirectedDFS(G, v);
    }

    boolean reachable(int v,int w){
        return directedDFS[v].marked(w);
    }

}
